package com.heyqing.topic.SearchInsert_0035;

import com.heyqing.topic.RemoveElement_0027.RemoveElement;

import java.util.Scanner;

/**
 * ClassName:SearchInsert
 * Package:com.heyqing.topic.SearchInsert_0035
 * Description:
 *
 * @Date:2024/9/9
 * @Author:Heyqing
 */
public class SearchInsert {
    /**
     * 搜索插入位置
     *
     * @param nums
     * @param target
     * @return
     */
    public int searchInsert(int[] nums, int target) {
        int index = 0, front = 0, end = nums.length - 1;
        if (nums[front] == target) return front;
        if (nums[end] == target) return end;
        if (nums.length <= 2) {
            if (nums.length == 1) {
                if (nums[0] == target) {
                    return 0;
                } else {
                    return target > nums[0] ? 1 : 0;
                }
            } else {
                if (target == nums[0] || target == nums[1]){
                    return target == nums[0] ? 0 : 1;
                }else {
                    if (target < nums[0]) return 0;
                    if (target > nums[1]) return 2;
                    else return 1;
                }
            }
        }
        while (front + 1 < end) {
            int mid = (front + end) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] > target) {
                end = mid;
                index = end;
                if (target < nums[front]) {
                    index = front;
                }
            } else {
                front = mid;
                index = front + 1;
                if (target > nums[end]) {
                    index = end + 1;
                }
            }
        }
        return index;
    }

    public static void start() {
        SearchInsert searchInsert = new SearchInsert();
        Scanner sc = new Scanner(System.in);
        System.out.println("请输入target:");
        int target = sc.nextInt();
        System.out.println("请输入nums的长度：");
        int len = sc.nextInt();
        int[] nums = new int[len];
        for (int i = 0; i < len; i++) {
            System.out.print("第" + (i + 1) + "个：");
            nums[i] = sc.nextInt();
        }
        int i = searchInsert.searchInsert(nums, target);
        System.out.println("下标为：" + i);
    }
}
